#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};

TreeNode* dfs(TreeNode* root)
{
    TreeNode* left = root->left, * right = root->right;
    TreeNode* last = root;
    root->left = nullptr;
    if (left != nullptr)
    {
        root->right = left;
        last = dfs(left);
    }
    if (right != nullptr)
    {
        last->right = right;
        last = dfs(right);
    }
    return last;
}

void flatten(TreeNode* root) {
    if (root == nullptr) return;
    dfs(root);
}